class Solution(object):
    def evaluate(self, s, knowledge):
        d = {}
        for key, value in knowledge:
            d[key] = value
        left = 0
        right = 0
        n = len(s)
        ans = []
        while right < n:
            if s[right] == '(':
                if right > left:
                    ans.append(s[left:right])
                left = right + 1
            else:
                if s[right] == ')':
                    c = s[left: right]
                    if c in d:
                        ans.append(d[c])
                    else:
                        ans.append('?')
                    left = right + 1
            right += 1
        if right > left:
            ans.append(s[left:right])
        return ''.join(ans)
